LeetCode 134 、加油站

一、题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

二、题目解析

证明命题：如果总的 gas 量大于 cost ，则一定有解。

1、当 n = 2 时，一定可以找到一个点 A ，它的 gas >= cost ；假设另一个点为 B ，则 A 点可以到达 B 点，到达 B 点之后总gas 量根据题设，大于 B 点的 cost ，所以也可以回到 A 点；

2、当n = 3 时，一定可以找到两个点，它们的 gas 之和大于等于 cost 之和，把他们当作一个整体点 A ，剩余的点为 B 。那么根据 n = 2 的情况，A 可以到达 B 再返回A 。对于 A 内部来说，它们也符合 n = 2 的情况，所以同样可以互通。

3、当 n > 3时，一定可以找到 n - 1 个点，它们的 gas 之和大于等于 cost 之和，把他们当作一个整体点 A ，剩余的点为B 。那么根据 n - 1 的情况，A 可以到达 B 再返回 A 。对于 A 内部来说，它们也符合 n - 1 的情况，所以同样可以互通。

所以，证明若 gas 总量大于 cost ，则一定有解。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 加油站（134）：https://leetcode-cn.com/problems/gas-station/
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {

        // 获取加油站的数量
        int n = gas.length;

        // 一开始，默认汽车储备的汽油数量为 0
        int remainGas = 0;

        // 需要统计一下，所有加油站的汽油总量能否支持汽车跑完所有的路程
        for( int i = 0 ; i < n ; i++ ){

            remainGas += gas[i] - cost[i];
        }

        // 如果发现加油站的汽油总量小于所有的路程需要消耗的汽油总量
        // 即汽车最终油箱汽油为负，那无论选择在哪出发，都不可能绕环路行驶一周
        if( remainGas < 0 ){

            return -1;
        }

        // 如果发现加油站的汽油总量大于或者等于所有的路程需要消耗的汽油总量
        // 那么可以绕环路行驶一周，接下来去寻找出发位置

        // 一开始，默认汽车此时储备的汽油数量为 0
        int currentGas = 0;

        // 一开始，默认汽车出发位置在索引为 0 的加油站
        int i = 0;

        // index 表示最终选择的出发点，默认为 0
        int index = 0;

        // 依次遍历每个加油站，在遍历的过程中，会执行一些【跳跃操作】
        while ( i < n ){

            // 汽车在 i 号加油站加了 gas[i]
            // 开到 i + 1 号加油站消耗了 cost[i] 的汽油
            currentGas += gas[i] - cost[i];
            
            // 如果发现油箱里面的汽油是非负数
            // 即汽车可以开到  j 号加油站，j >= i + 1，那么就让汽车继续尝试往前开
            // 寻找出从 i 号加油站出发到最远的加油站的位置 j ，在这期间汽车是会从中间的加油站加油的
            if( currentGas >= 0){

                i++;

            // 如果发现油箱里面的汽油是负数
            // 意味着汽车无法从 i 号加油站开到 j 号加油站，同时也意味着无法从 i + 1 号加油站开到 j 号加油站
            // 那么就直接尝试让汽车从 j 号加油站开始重新出发 
            }else{
                
                // 重新初始化汽车油箱油量
                currentGas = 0;

                // 最终选择的出发点为 j 号加油站
                index = i + 1;

                // 开始出发
                i++;
            }
        }

        // 最终找到了合适的出发点
        return index;
    }
}

**2、**C++ 代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
         // 获取加油站的数量
        int n = gas.size();

        // 一开始，默认汽车储备的汽油数量为 0
        int remainGas = 0;

        // 需要统计一下，所有加油站的汽油总量能否支持汽车跑完所有的路程
        for( int i = 0 ; i < n ; i++ ){

            remainGas += gas[i] - cost[i];
        }

        // 如果发现加油站的汽油总量小于所有的路程需要消耗的汽油总量
        // 即汽车最终油箱汽油为负，那无论选择在哪出发，都不可能绕环路行驶一周
        if( remainGas < 0 ){

            return -1;
        }

        // 如果发现加油站的汽油总量大于或者等于所有的路程需要消耗的汽油总量
        // 那么可以绕环路行驶一周，接下来去寻找出发位置

        // 一开始，默认汽车此时储备的汽油数量为 0
        int currentGas = 0;

        // 一开始，默认汽车出发位置在索引为 0 的加油站
        int i = 0;

        // index 表示最终选择的出发点，默认为 0
        int index = 0;

        // 依次遍历每个加油站，在遍历的过程中，会执行一些【跳跃操作】
        while ( i < n ){

            // 汽车在 i 号加油站加了 gas[i]
            // 开到 i + 1 号加油站消耗了 cost[i] 的汽油
            currentGas += gas[i] - cost[i];
            
            // 如果发现油箱里面的汽油是非负数
            // 即汽车可以开到  j 号加油站，j >= i + 1，那么就让汽车继续尝试往前开
            // 寻找出从 i 号加油站出发到最远的加油站的位置 j ，在这期间汽车是会从中间的加油站加油的
            if( currentGas >= 0){

                i++;

            // 如果发现油箱里面的汽油是负数
            // 意味着汽车无法从 i 号加油站开到 j 号加油站，同时也意味着无法从 i + 1 号加油站开到 j 号加油站
            // 那么就直接尝试让汽车从 j 号加油站开始重新出发 
            }else{
                
                // 重新初始化汽车油箱油量
                currentGas = 0;

                // 最终选择的出发点为 j 号加油站
                index = i + 1;

                // 开始出发
                i++;
            }
        }

        // 最终找到了合适的出发点
        return index;
    }
};

3、Python 代码

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 获取加油站的数量
        n = len(gas)

        # 一开始，默认汽车储备的汽油数量为 0
        remainGas = 0

        # 需要统计一下，所有加油站的汽油总量能否支持汽车跑完所有的路程
        for i in range(n) : 
            remainGas += gas[i] - cost[i]
        

        # 如果发现加油站的汽油总量小于所有的路程需要消耗的汽油总量
        # 即汽车最终油箱汽油为负，那无论选择在哪出发，都不可能绕环路行驶一周
        if remainGas < 0 :

            return -1

        # 如果发现加油站的汽油总量大于或者等于所有的路程需要消耗的汽油总量
        # 那么可以绕环路行驶一周，接下来去寻找出发位置

        # 一开始，默认汽车此时储备的汽油数量为 0
        currentGas = 0

        # 一开始，默认汽车出发位置在索引为 0 的加油站
        i = 0

        # index 表示最终选择的出发点，默认为 0
        index = 0

        # 依次遍历每个加油站，在遍历的过程中，会执行一些【跳跃操作】
        while i < n :

            # 汽车在 i 号加油站加了 gas[i]
            # 开到 i + 1 号加油站消耗了 cost[i] 的汽油
            currentGas += gas[i] - cost[i]
            
            # 如果发现油箱里面的汽油是非负数
            # 即汽车可以开到  j 号加油站，j >= i + 1，那么就让汽车继续尝试往前开
            # 寻找出从 i 号加油站出发到最远的加油站的位置 j ，在这期间汽车是会从中间的加油站加油的
            if currentGas >= 0:

                i+=1

            # 如果发现油箱里面的汽油是负数
            # 意味着汽车无法从 i 号加油站开到 j 号加油站，同时也意味着无法从 i + 1 号加油站开到 j 号加油站
            # 那么就直接尝试让汽车从 j 号加油站开始重新出发 
            else:
                
                # 重新初始化汽车油箱油量
                currentGas = 0

                # 最终选择的出发点为 j 号加油站
                index = i + 1

                # 开始出发
                i+=1


        # 最终找到了合适的出发点
        return index

四、复杂度分析

时间复杂度：O(N)，其中 N 为数组的长度。

空间复杂度：O(1)。